package tree;

import java.util.Arrays;

public class Solution124 {
    public static void main(String[] args) {
        TreeNode level5 = new TreeNode(-4);
        TreeNode level4 = new TreeNode(2, level5);
        TreeNode level3 = new TreeNode(4, null, level4);
        TreeNode level2 = new TreeNode(5, level3);
        TreeNode root = new TreeNode(-1, level2);
//        root.left = left;

        System.out.println(new Solution124().maxPathSum(root));

    }

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int[] rst = fetch(root);

        return Math.max(rst[2], rst[0] + rst[1] - root.val);
    }

    int[] fetch(TreeNode node) {
        // left, right, max
        int[] result = new int[]{0, 0, 0};
        if (node == null) {
            return result;
        }


        int[] rstLeftTree = fetch(node.left);
        int[] rstRightTree = fetch(node.right);


        int leftMax = node.val;
        int rightMax = node.val;
        int treeMax = Integer.MIN_VALUE;
        if (node.left != null) {
            leftMax = max(leftMax, node.val + rstLeftTree[0], node.val + rstLeftTree[1]);
            treeMax = Math.max(treeMax, rstLeftTree[2]);
        }

        if (node.right != null) {
            rightMax = max(rightMax, node.val + rstRightTree[0], node.val + rstRightTree[1]);
            treeMax = Math.max(treeMax, rstRightTree[2]);
        }

        treeMax = Math.max(treeMax, leftMax - node.val + rightMax);

        result[0] = leftMax;
        result[1] = rightMax;
        result[2] = treeMax;

        System.out.println("cur node: " + node.val + ", result: " + Arrays.toString(result));

        return result;
    }

    int max(int a, int b, int c) {
        return Math.max(Math.max(a, b), c);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int x) {
            val = x;
        }

        public TreeNode(int x, TreeNode left) {
            val = x;
            this.left = left;
        }

        public TreeNode(int x, TreeNode left, TreeNode right) {
            this(x, left);
            this.right = right;
        }
    }
}
